Setelah Tun Perak menjadi Bentara, beliau tidak digemari oleh Tun Ali, iaitu Bendahara Melaka ketika itu. Tun Ali yang berketurunan Tamil Muslim ketika itu sudahpun lanjut usianya. Perkara tersebut mengkhuatirkan sultan yang hendak melantik Tun Perak sebagai pengganti Tun Ali. Disebabkan risau dengan perbalahan antara pembesar yang memungkinkan kejatuhan pentadbiran negara, baginda mengahwinkan Tun Ali dengan Tun Kudu Tun Perpatih Sedang, iaitu kakak kepada Tun Perak dan isteri baginda sendiri. Baginda yang sanggup menceraikan Tun Kudu menerima keputusan yang dijangkakan bahawa Tun Ali sudahpun berbaik dengan Tun Perak.

Kemudian, baginda melantik Tun Perak sebagai Bendahara yang bergelar Paduka Raja pada tahun 1456 sementara Tun Ali, Bendahara keempat, dilantik sebagai Penghulu Bendahari dengan gelaran Seri Nara Diraja.

Ketika Tun Perak menjawat jawatan Bendahara, beliau telah menakluk negeri-negeri di pantai Selat Melaka seperti Rokan, Siak, Kampar dan Inderagiri di pulau Sumatera serta Johor, Pahang, Kelantan, Terengganu dan Perak yang menjadikan semua negeri ini sebagai jajahan takluk Melaka manakala Kedah pula menjadi negeri naungan Melaka. Dengan ini, Melaka telah menjadi sebuah empayar yang besar. Tidak kurang juga bagi aspek lain apabila Melaka membangun sehingga mencapai kekuatan dari segi politik, sosial, dan ekonominya. Kepesatan pembangunan di Melaka telah menarik banyak pedagang asing dari China, India, Timur Tengah, serta negara-negara jiran yang lain.